package com.xiaoyu.arrays;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @program: DS_and_A
 * @description: 数组中重复的数字
 *
 *找出数组中重复的数字。
 *
 * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
 * 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
 * 请找出数组中任意一个重复的数字。
 *
 * 示例 1：
 * 输入：
 * [2, 3, 1, 0, 2, 5, 3]
 * 输出：2 或 3
 *
 * @author: YuWenYi
 * @create: 2021-05-28 21:30
 **/
public class FindRepeatNumber_Offer03 {

    //解法一:使用map,key为num,value为num的次数
    public static int findRepeatNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)){
                map.put(num, map.get(num) + 1);
            }else {
                map.put(num, 1);
            }
        }
        for (Integer num : map.keySet()) {
            if (map.get(num) > 1){
                return num;
            }
        }
        throw new RuntimeException();
    }

    //解法二:摆脱hashmap,使用sort
    public static int findRepeatNumber1(int[] nums) {
        Arrays.parallelSort(nums);
        //数字大小为0-len-1
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i+1]){
                return nums[i];
            }
        }
        return 0;
    }

    //解法三:使用set
    public static int findRepeatNumber2(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)){
                return num;
            }
            set.add(num);
        }
        return -1;
    }

    //解法四:使用索引原地交换法
    /*
    * 3、如果有重复元素，例如:
     nums[i]     1  2  3  2    萝卜
         i       0  1  2  3    坑
    同样的，0号坑不要1号，先和1号坑交换，交换完这样的：

     nums[i]     2  1  3  2    萝卜
         i       0  1  2  3    坑
    0号坑不要2号萝卜，去和2号坑交换，交换完这样的：

     nums[i]     3  1  2  2    萝卜
         i       0  1  2  3    坑
    0号坑不要3号萝卜，去和3号坑交换，交换完这样的：

     nums[i]     2  1  2  3    萝卜
         i       0  1  2  3    坑
    0号坑不要2号萝卜，去和2号坑交换，结果发现你2号坑也是2号萝卜，那我还换个锤子，同时也说明有重复元素出现。
    *
    * */
    public static int findRepeatNumber3(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            if (i == nums[i]){  //num[i]已经在它应该在的地方,因此直接返回
                i++;
                continue;
            }
            if (nums[nums[i]] == nums[i]) return nums[i];
            //交换两个索引处的位置,将该值放到它对应的索引处,即最终需要i == nums[i]
            int temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
        return -1;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{0, 1, 2, 3, 4, 11, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
        System.out.println(findRepeatNumber3(nums));
    }
}
